package com.cty.A_GeneralDataStructures.D_HashTable.OpenAddress;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/15 8:22
 * @Description: 线性探测的开放地址法 哈希表
 * 应用场景：
 *      当数据量大时，考虑哈希表或树
 *          当数据量可预测且对查找、插入速度要求高时，考虑哈希表
 *              使用开放地址法时，若内存充足可以保证装填因子低于1/2，三种方法存取性能都比较好，但线性探测法最简单，建议选择线性探测法
 * 重要操作：
 *      ① find(long): DataItem    O(1)
 *      ② insert(DataItem): void    O(1)
 *      ③ delete(long): DataItem    O(1)
 * @version: 1.0
 */
public class HashTable {
    private int maxSize;  // 为减少聚集，容量应为质数
    private DataItem[] array;
    private DataItem nonItem;  // 删除标识节点

    public HashTable(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nonItem = new DataItem(-1);
    }

    public void displayHashTable(){
        for(int i=0; i<maxSize; i++)
            if(array[i] != null)
                System.out.print(array[i].getKey() + " ");
            else
                System.out.print("-- ");
        System.out.println();
    }

    private int hashFunc(long key){
        return (int)(key % maxSize);
    }

    /**
     * 线性查找  O(1) 聚集不严重时
     * @param key
     * @return
     */
    public DataItem find(long key){
        int hashValue = hashFunc(key);

        while(array[hashValue] != null){  // 遇到空位结束
            if(array[hashValue].getKey() == key)  // 找到结束
                return array[hashValue];

            hashValue = (hashValue + 1) % maxSize;  // 线性探测，到表尾回表头
        }  // end while
        return null;
    }  // end find()

    /**
     * 线性插入  O(1) 聚集不严重时
     * @param item
     */
    public void insert(DataItem item){  // 保证容量充足，一定能能插入成功
        int hashValue = hashFunc(item.getKey());

        while(array[hashValue]!=null && array[hashValue].getKey()!=-1)  // 遇到空位或删除标识节点结束
            hashValue = (hashValue + 1) % maxSize;

        array[hashValue] = item;
    }  // end insert()

    /**
     * 线性删除  O(1) 聚集不严重时
     * @param key
     * @return
     */
    public DataItem delete(long key){
        int hashValue = hashFunc(key);

        while(array[hashValue] != null){  // 遇到空位结束
            if(array[hashValue].getKey() == key){  // 查找到结束
                DataItem temp = array[hashValue];
                array[hashValue] = nonItem;
                return temp;
            }
            hashValue = (hashValue + 1) % maxSize;
        }  // end while
        return null;
    }  // end delete()

}  // end HashTable{}

/**
 * Enter size of hash table: 11
 * Enter initial number of items: 6
 * Enter first letter of show, insert, delete or find: s
 * 44 -- 57 102 59 16 -- -- -- -- 43
 * Enter first letter of show, insert, delete or find: i
 * Enter key value to insert: 11
 * Enter first letter of show, insert, delete or find: s
 * 44 11 57 102 59 16 -- -- -- -- 43
 * Enter first letter of show, insert, delete or find: i
 * Enter key value to insert: 8
 * Enter first letter of show, insert, delete or find: s
 * 44 11 57 102 59 16 -- -- 8 -- 43
 * Enter first letter of show, insert, delete or find: d
 * Enter key value to delete: 102
 * Enter first letter of show, insert, delete or find: s
 * 44 11 57 -1 59 16 -- -- 8 -- 43
 * Enter first letter of show, insert, delete or find: f
 * Enter key value to find: 59
 * Found 59
 * Enter first letter of show, insert, delete or find: i
 * Enter key value to insert: 102
 * Enter first letter of show, insert, delete or find: s
 * 44 11 57 102 59 16 -- -- 8 -- 43
 */
